# 用字典的方式存储每个节点的child
class Trie(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.child = {}

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: None
        """
        cur_node = self.child
        for s in word:
            if s not in cur_node.keys():
                cur_node[s] = {}
            cur_node = cur_node[s]
        # 插入结束符
        cur_node['#'] = '#'

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        cur_node = self.child
        for s in word:
            if s in cur_node.keys():
                cur_node = cur_node[s]
            else:
                return False
        return '#' in cur_node.keys()

    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        cur_node = self.child
        for s in prefix:
            if s in cur_node.keys():
                cur_node = cur_node[s]
            else:
                return False
        return True


obj = Trie()
obj.insert('apple')
obj.insert('apply')
print(obj.search('appl'))
print(obj.startsWith('app'))
